/*
 * @lc app=leetcode.cn id=2300 lang=cpp
 * @lcpr version=30204
 *
 * [2300] 咒语和药水的成功对数
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        // 对药水数组进行排序，为二分查找做准备
        sort(potions.begin(), potions.end());
        vector<int> result;
        int m = potions.size();

        for (int s : spells) {
            // 计算当前咒语需要的最小药水强度（向上取整）
            long long min_potion = (success + s - 1) / s;
            // 找到第一个大于等于最小强度的药水位置
            auto it = lower_bound(potions.begin(), potions.end(), min_potion);
            // 从该位置到数组末尾的所有药水都符合条件
            result.push_back(potions.end() - it);
        }
        
        return result;
    }
};
// @lc code=end



/*
// @lcpr case=start
// [5,1,3]\n[1,2,3,4,5]\n7\n
// @lcpr case=end

// @lcpr case=start
// [3,1,2]\n[8,5,8]\n16\n
// @lcpr case=end

 */

